package lib

func init() {
	Probs = append(Probs, Problem{
		Num:         763,
		Discription: "尽可能将字符串划分成更多子串，每个字母最多出现在一个子串",
		Level:       2,
		Labels: map[string]int{
			"哈希表":  1,
			"滑动窗口": 1,
		},
	})
}

func PartitionLabels(s string) []int {
	//统计所有字母的出现次数
	chCount := make(map[byte]int, 26)
	for i := range s {
		chCount[s[i]]++
	}

	res := make([]int, 0)
	start := 0
	i := 0
	for i < len(s) {
		count := 0
		chMap := make(map[byte]bool, 0)
		//子串长度==0 or 当前子串中有字母数量不够
		for i < len(s) && (len(chMap) == 0 || count > 0) {
			ch := s[i]
			//已经存在与子串，还需字母数量--
			if chMap[ch] {
				count--
			} else {
				//如果是个新字符，就还需新增chCount[ch] - 1个字符
				chMap[ch] = true
				count += chCount[ch] - 1
			}
			i++
		}
		res = append(res, i-start)
		start = i
	}

	return res
}
